package cxydmmszl.chapter03.t049.simple;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 在二叉树中找到两个节点的最近公共祖先
 * <li style="color: green;">Desc</li>
 * 给定一棵二叉树以及这棵树上的两个节点 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。
 * <li style="color: green;">Input</li>
 * 第一行输入两个整数 n 和 root，n 表示二叉树的总节点个数，root 表示二叉树的根节点。<br/>
 * 以下 n 行每行三个整数 fa，lch，rch，表示 fa 的左儿子为 lch，右儿子为 rch。
 * (如果 lch 为 0 则表示 fa 没有左儿子，rch同理)<br/>
 * 最后一行为节点 o1 和 o2。
 * <li style="color: green;">Output</li>
 * 输出一个整数表示答案。
 * <li style="color: blue;">Link</li> CD176, CD177, CD178
 *
 * @author habitplus
 * @since 2021-09-07 15:33
 */
public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = bf.readLine().split(" ");
        int n = Integer.parseInt(ss[0]);
        int root = Integer.parseInt(ss[1]);
        int fa, lch, rch, o1, o2;
        Map<Integer, TreeNode> map = new HashMap<>();
        Map<Integer, int[]> child = new HashMap<>();
        for (int i = 0; i < n; i++) {
            ss = bf.readLine().split(" ");
            fa = Integer.parseInt(ss[0]);
            lch = Integer.parseInt(ss[1]);
            rch = Integer.parseInt(ss[2]);

            map.put(fa, new TreeNode(fa));
            child.put(fa, new int[]{lch, rch});
        }
        ss = bf.readLine().split(" ");
        o1 = Integer.parseInt(ss[0]);
        o2 = Integer.parseInt(ss[1]);
        bf.close();

        // 建树
        for (Map.Entry<Integer, int[]> ch : child.entrySet()) {
            map.get(ch.getKey()).left = map.get(ch.getValue()[0]);
            map.get(ch.getKey()).right = map.get(ch.getValue()[1]);
        }

        TreeNode node = lowestAncestor1(map.get(root), map.get(o1), map.get(o2));
        System.out.println(node.val);

    }

    private static TreeNode lowestAncestor1(TreeNode root, TreeNode o1, TreeNode o2) {
        if (root == null || root == o1 || root == o2) {
            return root;
        }
        // 在左右子树上继续查找
        TreeNode left = lowestAncestor1(root.left, o1, o2);
        TreeNode right = lowestAncestor1(root.right, o1, o2);

        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
}
